'''
https://www.luogu.com.cn/problem/P4145
支持区间MOD的线段树 单点势能: log v 以2为底
支持区间查询
支持单点更新（题目的原因，保证了整体复杂度或者说单点势能不会过高）
'''

class SegmentTree:

    def __init__(self, nums):
        self.n = n = len(nums)
        self.info_sum = [0] * (n << 2)
        self.info_max = [0] * (n << 2)
        self._build(nums)

    def _up(self, root):
        self.info_sum[root] = self.info_sum[root << 1] + self.info_sum[root << 1 | 1]
        self.info_max[root] = max(self.info_sum[root << 1], self.info_sum[root << 1 | 1])

    def _build(self, nums):
        def f(l, r, root):
            if l == r:
                self.info_max[root] = self.info_sum[root] = nums[l - 1]
                return
            mid = (l + r) >> 1
            f(l, mid, root << 1)
            f(mid + 1, r, root << 1 | 1)
            self._up(root)

        f(1, self.n, 1)

    def query(self, L, R):
        def f(l, r, root):
            if r < L or l > R: return 0
            if L <= l and r <= R: return self.info_sum[root]
            mid = (l + r) >> 1
            return f(l, mid, root << 1) + f(mid + 1, r, root << 1 | 1)

        return f(1, self.n, 1)

    def mod(self, L, R, X):
        def f(l, r, root):
            # !!! 剪枝
            if r < L or l > R or self.info_max[root] < X: return
            # 没有懒更新操作，just do it，但有剪枝
            if l == r:
                self.info_sum[root] = self.info_max[root] = self.info_sum[root] % X
                return
            mid = (l + r) >> 1
            f(l, mid, root << 1)
            f(mid + 1, r, root << 1 | 1)
            self._up(root)

        f(1, self.n, 1)

    def update(self, I, V):
        def f(l, r, root):
            # 剪枝，如果这个区间的最大值<=1了(题目保证最小值为1)，就不需要sqrt了
            if r < I or l > I: return
            # 没有懒更新操作，just do it，但有剪枝
            if l == r:
                self.info_sum[root] = self.info_max[root] = V
                return
            mid = (l + r) >> 1
            f(l, mid, root << 1)
            f(mid + 1, r, root << 1 | 1)
            self._up(root)

        f(1, self.n, 1)


import sys

n, m = map(int, sys.stdin.readline().split())
nums = list(map(int, sys.stdin.readline().split()))
tree = SegmentTree(nums)
res = []
for line in sys.stdin.readlines():
    ops = list(map(int, line.split()))
    if ops[0] == 2:
        tree.mod(ops[1], ops[2], ops[3])
    elif ops[0] == 3:
        tree.update(ops[1], ops[2])
    else:
        res.append(str(tree.query(ops[1], ops[2])))
sys.stdout.write('\n'.join(res))
